package com.order.www;

import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
 * 例如:
 * 给定s=“nowcode”；
 * dict=["now", "code"].
 * 返回true，因为"nowcode"可以被分割成"now code".
 * User:yxd
 * Date:2022-03-23
 * Time:22:17
 */
public class Dp4 {
    public boolean wordBreak(String s, Set<String> dict) {
        //动态规划
        //状态定义:前面的在词组中能找到，后面的也能找到
        //状态转移方程：(i < j) && F（i,j）&& F(j + 1,len)
        //初值：F（0,0）= true;
        if(s == null || dict.isEmpty()){
            return false;
        }
        int len = s.length();
        boolean[] flg = new boolean[len + 1];
        flg[0] = true;
        for(int i = 1;i <= len;i ++){
            for(int j = i - 1;j >= 0;j --){
                if(flg[j] && dict.contains(s.substring(j,i))){
                    flg[i] = true;
                    break;
                }
            }
        }
        return flg[len];
    }
}
